home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / pthread_alloc.h < prev    next >
C/C++ Source or Header  |  1997-05-28  |  11KB  |  385 lines
  1. /*
  2.  * Copyright (c) 1996
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. /*
  15.  *
  16.  * Copyright (c) 1997
  17.  * Moscow Center for SPARC Technology
  18.  *
  19.  * Permission to use, copy, modify, distribute and sell this software
  20.  * and its documentation for any purpose is hereby granted without fee,
  21.  * provided that the above copyright notice appear in all copies and
  22.  * that both that copyright notice and this permission notice appear
  23.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  24.  * representations about the suitability of this software for any
  25.  * purpose.  It is provided "as is" without express or implied warranty.
  26.  *
  27.  */
  28.  
  29.  
  30. #ifndef __SGI_STL_PTHREAD_ALLOC_H
  31. #define __SGI_STL_PTHREAD_ALLOC_H
  32.  
  33. // Pthread-specific node allocator.
  34. // This is similar to the default allocator, except that free-list
  35. // information is kept separately for each thread, avoiding locking.
  36. // This should be reasonably fast even in the presence of threads.
  37. // The down side is that storage may not be well-utilized.
  38. // It is not an error to allocate memory in thread A and deallocate
  39. // it n thread B.  But this effectively transfers ownership of the memory,
  40. // so that it can only be reallocated by thread B.  Thus this can effectively
  41. // result in a storage leak if it's done on a regular basis.
  42. // It can also result in frequent sharing of
  43. // cache lines among processors, with potentially serious performance
  44. // consequences.
  45.  
  46.  
  47. #include <stddef.h>
  48. #include <stdlib.h>
  49. #include <string.h>
  50. #include <pthread.h>
  51. # ifndef __SGI_STL_ALLOC_H
  52. #  include <alloc.h>
  53. # endif
  54. #ifndef __RESTRICT
  55. #  define __RESTRICT
  56. #endif
  57.  
  58. # if defined ( __STL_USE_ABBREVS )
  59. // ugliness is intentional - to reduce conflicts
  60. #  define __pthread_alloc_template   _pTHr_Al
  61. # endif
  62.  
  63. __BEGIN_STL_NAMESPACE
  64.  
  65. // Note that this class has nonstatic members.  We instantiate it once
  66. // per thread.
  67. template <bool dummy>
  68. class __pthread_alloc_template {
  69.  
  70. private:
  71.   enum {ALIGN = 8};
  72.   enum {MAX_BYTES = 128};  // power of 2
  73.   enum {NFREELISTS = MAX_BYTES/ALIGN};
  74.  
  75.   union obj {
  76.         union obj * free_list_link;
  77.         char client_data[ALIGN];    /* The client sees this.        */
  78.   };
  79.  
  80.   // Per instance state
  81.   obj* volatile free_list[NFREELISTS]; 
  82.   __pthread_alloc_template<dummy>* next;     // Free list link
  83.  
  84.   static size_t ROUND_UP(size_t bytes) {
  85.     return (((bytes) + ALIGN-1) & ~(ALIGN - 1));
  86.   }
  87.   static size_t FREELIST_INDEX(size_t bytes) {
  88.     return (((bytes) + ALIGN-1)/ALIGN - 1);
  89.   }
  90.  
  91.   // Returns an object of size n, and optionally adds to size n free list.
  92.   void *refill(size_t n);
  93.   // Allocates a chunk for nobjs of size size.  nobjs may be reduced
  94.   // if it is inconvenient to allocate the requested number.
  95.   static char *chunk_alloc(size_t size, int &nobjs);
  96.  
  97.   // Chunk allocation state. And other shared state.
  98.   // Protected by chunk_allocator_lock.
  99.   static pthread_mutex_t chunk_allocator_lock;
  100.   static char *start_free;
  101.   static char *end_free;
  102.   static size_t heap_size;
  103.   static __pthread_alloc_template<dummy>* free_allocators;
  104.   static pthread_key_t key;
  105.   static bool key_initialized;
  106.     // Pthread key under which allocator is stored. 
  107.     // Allocator instances that are currently unclaimed by any thread.
  108.   static void destructor(void *instance);
  109.     // Function to be called on thread exit to reclaim allocator
  110.     // instance.
  111.   static __pthread_alloc_template<dummy> *new_allocator();
  112.     // Return a recycled or new allocator instance.
  113.   static __pthread_alloc_template<dummy> *get_allocator_instance();
  114.     // ensure that the current thread has an associated
  115.     // allocator instance.
  116.   class lock {
  117.       public:
  118.     lock () { pthread_mutex_lock(&chunk_allocator_lock); }
  119.     ~lock () { pthread_mutex_unlock(&chunk_allocator_lock); }
  120.   };
  121.   friend class lock;
  122.  
  123.  
  124. public:
  125.  
  126.   __pthread_alloc_template() : next(0)
  127.   {
  128.     memset((void *)free_list, 0, NFREELISTS * sizeof(obj *));
  129.   }
  130.  
  131.   /* n must be > 0    */
  132.   static void * allocate(size_t n)
  133.   {
  134.     obj * volatile * my_free_list;
  135.     obj * __RESTRICT result;
  136.     __pthread_alloc_template<dummy>* a;
  137.  
  138.     if (n > MAX_BYTES) {
  139.     return(malloc(n));
  140.     }
  141.     if (!key_initialized ||
  142.         !(a = (__pthread_alloc_template<dummy>*)
  143.         pthread_getspecific(key))) {
  144.     a = get_allocator_instance();
  145.     }
  146.     my_free_list = a -> free_list + FREELIST_INDEX(n);
  147.     result = *my_free_list;
  148.     if (result == 0) {
  149.         void *r = a -> refill(ROUND_UP(n));
  150.     return r;
  151.     }
  152.     *my_free_list = result -> free_list_link;
  153.     return (result);
  154.   };
  155.  
  156.   /* p may not be 0 */
  157.   static void deallocate(void *p, size_t n)
  158.   {
  159.     obj *q = (obj *)p;
  160.     obj * volatile * my_free_list;
  161.     __pthread_alloc_template<dummy>* a;
  162.  
  163.     if (n > MAX_BYTES) {
  164.     free(p);
  165.     return;
  166.     }
  167.     if (!key_initialized ||
  168.         !(a = (__pthread_alloc_template<dummy>*)
  169.         pthread_getspecific(key))) {
  170.     a = get_allocator_instance();
  171.     }
  172.     my_free_list = a->free_list + FREELIST_INDEX(n);
  173.     q -> free_list_link = *my_free_list;
  174.     *my_free_list = q;
  175.   }
  176.  
  177.   static void * reallocate(void *p, size_t old_sz, size_t new_sz);
  178.  
  179. } ;
  180.  
  181. typedef __pthread_alloc_template<false> pthread_alloc;
  182.  
  183.  
  184. template <bool dummy>
  185. void __pthread_alloc_template<dummy>::destructor(void * instance)
  186. {
  187.     __pthread_alloc_template<dummy>* a =
  188.     (__pthread_alloc_template<dummy>*)instance;
  189.     a -> next = free_allocators;
  190.     free_allocators = a;
  191. }
  192.  
  193. template <bool dummy>
  194. __pthread_alloc_template<dummy>*
  195. __pthread_alloc_template<dummy>::new_allocator()
  196. {
  197.     if (0 != free_allocators) {
  198.     __pthread_alloc_template<dummy>* result = free_allocators;
  199.     free_allocators = free_allocators -> next;
  200.     return result;
  201.     } else {
  202.     return new __pthread_alloc_template<dummy>;
  203.     }
  204. }
  205.  
  206. template <bool dummy>
  207. __pthread_alloc_template<dummy>*
  208. __pthread_alloc_template<dummy>::get_allocator_instance()
  209. {
  210.     __pthread_alloc_template<dummy>* result;
  211.     if (!key_initialized) {
  212.         /*REFERENCED*/
  213.     lock lock_instance;
  214.     if (!key_initialized) {
  215.         if (pthread_key_create(&key, destructor)) {
  216.         abort();  // failed
  217.         }
  218.         key_initialized = true;
  219.     }
  220.     }
  221.     result = new_allocator();
  222.     if (pthread_setspecific(key, result)) abort();
  223.     return result;
  224. }
  225.  
  226. /* We allocate memory in large chunks in order to avoid fragmenting    */
  227. /* the malloc heap too much.                        */
  228. /* We assume that size is properly aligned.                */
  229. template <bool dummy>
  230. char *__pthread_alloc_template<dummy>
  231. ::chunk_alloc(size_t size, int &nobjs)
  232. {
  233.   {
  234.     char * result;
  235.     size_t total_bytes;
  236.     size_t bytes_left;
  237.     /*REFERENCED*/
  238.     lock lock_instance;        // Acquire lock for this routine
  239.  
  240.     total_bytes = size * nobjs;
  241.     bytes_left = end_free - start_free;
  242.     if (bytes_left >= total_bytes) {
  243.     result = start_free;
  244.     start_free += total_bytes;
  245.     return(result);
  246.     } else if (bytes_left >= size) {
  247.     nobjs = bytes_left/size;
  248.     total_bytes = size * nobjs;
  249.     result = start_free;
  250.     start_free += total_bytes;
  251.     return(result);
  252.     } else {
  253.     size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
  254.     // Try to make use of the left-over piece.
  255.     if (bytes_left > 0) {
  256.         __pthread_alloc_template<dummy>* a = 
  257.         (__pthread_alloc_template<dummy>*)pthread_getspecific(key);
  258.         obj * volatile * my_free_list =
  259.             a->free_list + FREELIST_INDEX(bytes_left);
  260.  
  261.             ((obj *)start_free) -> free_list_link = *my_free_list;
  262.             *my_free_list = (obj *)start_free;
  263.     }
  264. #    ifdef _SGI_SOURCE
  265.       // Try to get memory that's aligned on something like a
  266.       // cache line boundary, so as to avoid parceling out
  267.       // parts of the same line to different threads and thus
  268.       // possibly different processors.
  269.       {
  270.         const int cache_line_size = 128;  // probable upper bound
  271.         bytes_to_get &= ~(cache_line_size-1);
  272.         start_free = (char *)memalign(cache_line_size, bytes_to_get); 
  273.         if (0 == start_free) {
  274.           start_free = (char *)malloc_alloc::allocate(bytes_to_get);
  275.         }
  276.       }
  277. #    else  /* !SGI_SOURCE */
  278.       start_free = (char *)malloc_alloc::allocate(bytes_to_get);
  279. #       endif
  280.     heap_size += bytes_to_get;
  281.     end_free = start_free + bytes_to_get;
  282.     }
  283.   }
  284.   // lock is released here
  285.   return(chunk_alloc(size, nobjs));
  286. }
  287.  
  288.  
  289. /* Returns an object of size n, and optionally adds to size n free list.*/
  290. /* We assume that n is properly aligned.                */
  291. /* We hold the allocation lock.                        */
  292. template <bool dummy>
  293. void *__pthread_alloc_template<dummy>
  294. ::refill(size_t n)
  295. {
  296.     int nobjs = 128;
  297.     char * chunk = chunk_alloc(n, nobjs);
  298.     obj * volatile * my_free_list;
  299.     obj * result;
  300.     obj * current_obj, * next_obj;
  301.     int i;
  302.  
  303.     if (1 == nobjs)  {
  304.     return(chunk);
  305.     }
  306.     my_free_list = free_list + FREELIST_INDEX(n);
  307.  
  308.     /* Build free list in chunk */
  309.       result = (obj *)chunk;
  310.       *my_free_list = next_obj = (obj *)(chunk + n);
  311.       for (i = 1; ; i++) {
  312.     current_obj = next_obj;
  313.     next_obj = (obj *)((char *)next_obj + n);
  314.     if (nobjs - 1 == i) {
  315.         current_obj -> free_list_link = 0;
  316.         break;
  317.     } else {
  318.         current_obj -> free_list_link = next_obj;
  319.     }
  320.       }
  321.     return(result);
  322. }
  323.  
  324. template <bool dummy>
  325. void *__pthread_alloc_template<dummy>
  326. ::reallocate(void *p, size_t old_sz, size_t new_sz)
  327. {
  328.     void * result;
  329.     size_t copy_sz;
  330.  
  331.     if (old_sz > MAX_BYTES && new_sz > MAX_BYTES) {
  332.     return(realloc(p, new_sz));
  333.     }
  334.     if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
  335.     result = allocate(new_sz);
  336.     copy_sz = new_sz > old_sz? old_sz : new_sz;
  337.     memcpy(result, p, copy_sz);
  338.     deallocate(p, old_sz);
  339.     return(result);
  340. }
  341.  
  342.  
  343. #if ( __STL_STATIC_TEMPLATE_DATA > 0 )
  344. template <bool dummy>
  345. __pthread_alloc_template<dummy> *
  346. __pthread_alloc_template<dummy>::free_allocators = 0;
  347.  
  348. template <bool dummy>
  349. pthread_key_t __pthread_alloc_template<dummy>::key;
  350.  
  351. template <bool dummy>
  352. bool __pthread_alloc_template<dummy>::key_initialized = false;
  353.  
  354. template <bool dummy>
  355. pthread_mutex_t __pthread_alloc_template<dummy>::chunk_allocator_lock
  356. = PTHREAD_MUTEX_INITIALIZER;
  357.  
  358. template <bool dummy>
  359. char *__pthread_alloc_template<dummy>
  360. ::start_free = 0;
  361.  
  362. template <bool dummy>
  363. char *__pthread_alloc_template<dummy>
  364. ::end_free = 0;
  365.  
  366. template <bool dummy>
  367. size_t __pthread_alloc_template<dummy>
  368. ::heap_size = 0;
  369.  
  370. #else 
  371. __DECLARE_INSTANCE(pthread_alloc *, pthread_alloc::free_allocators,0);
  372. __DECLARE_INSTANCE(pthread_key_t,  pthread_alloc::key,0);
  373. __DECLARE_INSTANCE(bool, pthread_alloc::key_initialized, 0);
  374. __DECLARE_INSTANCE(pthread_mutex_t, pthread_alloc::chunk_allocator_lock, 
  375.                    PTHREAD_MUTEX_INITIALIZER);
  376. __DECLARE_INSTANCE(char *, pthread_alloc::start_free,0);
  377. __DECLARE_INSTANCE(char *, pthread_alloc::end_free,0);
  378. __DECLARE_INSTANCE(size_t, pthread_alloc::heap_size, 0);
  379. #endif /* ( __STL_STATIC_TEMPLATE_DATA > 0 ) */
  380.  
  381. __END_STL_NAMESPACE
  382.  
  383.  
  384. #endif /* __NODE_ALLOC_H */
  385.